The invention pertains to the storage of data in a cache, and more particularly to the efficient storage of prediction information such as branch prediction information in a cache. Branch prediction information is information which predicts whether an instruction of the form xe2x80x9cbranch to instruction X if condition Y is metxe2x80x9d will require the branch to be taken or not taken.
If branch prediction is to be based on an algorithm other than xe2x80x9cbranches are always predicted takenxe2x80x9d or xe2x80x9cbranches are always predicted not takenxe2x80x9d, some means must exist for storing branch prediction information. Frequently, such a means comprises a table of 2-bit branch prediction history counts which are respectively incremented or decremented in response to branch instructions being taken or not taken.
Many of today""s microprocessors incorporate structures known as instruction pipelines. Instruction pipelines increase the efficiency of a processor by enabling a processor to simultaneously process a plurality of instructions. Instruction pipelines can be thought of as instruction assembly lines. Instructionxe2x80x940 enters the first stage of the pipeline while Instructionxe2x80x941 is simultaneously processed in the second stage of the pipeline, Instructionxe2x80x942 is simultaneously processed in the third stage of the pipeline, and so on. Periodically, a new instruction is clocked into the instruction pipeline, and each instruction being processed in the pipeline is passed to the next stage of the pipeline, or is output from the pipeline.
To maximize instruction execution efficiency, it is desirable to keep instruction pipelines full as often as possible (with an instruction being processed in each stage of the pipeline) such that each periodic clocking of the instruction pipeline produces a useful output. However, whenever 1) there has been a transfer of program flow control from one section of program code to another, 2) instructions have been speculatively fetched and processed, and 3) it is determined that the speculatively fetched and processed instructions should not have been processed, an instruction pipeline will produce an output that is not useful. For each clock cycle that an instruction pipeline produces an output that is not useful, the instruction pipeline has a negative impact on a processor""s efficiency.
Program flow control instructions such as branch instructions are one means by which program flow control can be transferred from one section of program code to another. Branch instructions can be conditional or unconditional. A conditional branch instruction determines program flow control based on the resolution of a specified condition. An unconditional branch instruction always results in a transfer of program flow control.
xe2x80x9cBranch to instruction X if A greater than Bxe2x80x9d is one example of a conditional branch instruction. If A greater than B, program control flow will transfer to a section of program code beginning with instruction X (i.e., a target code section). If Axe2x89xa6B, program control flow will continue with a section of program code which sequentially follows the conditional branch instruction (i.e., a sequential code section).
Since instruction pipelines can be several stages deep, conditional branch instructions are often fetched before the conditions specified in the branch instructions can be resolved. A processor must therefore predict whether branches will be taken or not taken. After a prediction is made, instructions are speculatively fetched from either a target code section (if a branch is predicted to be taken) or a sequential code section (if a branch is predicted to be not taken).
Although many branch prediction algorithms exist, mispredictions still occur. By the time a misprediction is identified, it is possible for an instruction pipeline to be operating on many instructions which were fetched from an incorrect code section. On encountering such a misprediction, misfetched instructions which are being processed in one or more pipelines must be flushed from the pipelines, and instructions from the correct code section must be fetched and processed through the pipelines.
When flushing instructions from a pipeline, bubbles (or gaps) are injected into the pipeline. Unfortunately, pipeline flushing sometimes makes it necessary to clock a pipeline through several clock cycles before the instruction pipeline can once again produce a useful output. Since conditional branch instructions and other program flow control instructions are prevalent in program code (e.g., sometimes on the order of once every five instructions), the cumulative effect of branch misprediction can have a significant and detrimental impact on a processor""s performance, even when branch prediction accuracy is relatively high.
A table of branch prediction history counts can be stored in any one of a number of cache types, including a direct mapped cache, a set-associative cache, and a non-tagged, n-way cache. However, most forms of these caches suffer from cache conflicts and/or aliasing.
Assuming that a cache is designed to store a table of branch prediction history counts, a cache conflict occurs when a count associated with address A and a count associated with address B need to be stored in the same cache entry. Cache conflicts may be reduced by, for example, increasing the size of a cache or implementing the cache as a set-associative cache (i.e., storing tags in a cache) or non-tagged, n-way cache.
Aliasing occurs when an attempt is made to read a count associated with address A from a cache, and instead, a count associated with address B is read from the cache. Aliasing can therefore lead to false hits being generated by a cache (i.e., a hit on data which is not the desired data).
Aliasing typically assumes one of three forms: compulsory aliasing, capacity aliasing or conflict aliasing. Compulsory aliasing occurs when an attempt to read a count associated with address A is made prior to an initialization of the count. One way to mitigate compulsory aliasing is to initialize the entries of a cache to one or more predetermined count values.
Capacity aliasing occurs when a working number of counts which need to be stored in a cache exceeds the number of cache entries which are available for storing the counts. One way to mitigate capacity aliasing is to increase the number of entries in a cache.
Conflict aliasing occurs as a result of a cache conflict. Conflict aliasing can be reduced by, for example, making a cache larger, implementing a cache as a set-associative cache, or implementing a cache as a non-tagged, n-way cache.
In a direct mapped cache of 2-bit counts, each count may be directly addressed by, for example, a number of bits of an instruction pointer. Unfortunately, a direct mapped cache is not a very effective means for storing branch prediction information, since cache conflicts and aliasing can only be reduced by increasing the size of the cache, and chip area for implementing a branch prediction cache is typically very limited.
One alternative to a direct mapped cache of 2-bit counts is a set-associative cache of 2-bit counts. In a set-associative cache, each count is stored with a tag, and a count is addressed by first reading a line of n counts from the cache (i.e., one count from each of the n ways, or a xe2x80x9csetxe2x80x9d of counts), and then comparing the tag of a requested count with the tags of the n counts which were just read. Cache conflicts can still occur, but the storage of tags helps to keep a cache conflict from leading to conflict aliasing. In fact, aliasing can be eliminated if complete tags are stored with the counts. Complete tags are tags which enable counts to be uniquely addressed. As the size of a tag is decreased, aliasing tends to increase. However, a smaller set-associative cache can achieve results which are comparable to those of a much larger direct mapped cache. One drawback to storing data such as 2-bit counts in a set-associative cache is that tags which are large enough to mitigate aliasing to an acceptable level will typically be much larger than the 2-bit counts which they help to identify. As a result, the data stored in such a cache comprises much more tag information than branch prediction information, and the xe2x80x9coverheadxe2x80x9d:xe2x80x9cprediction informationxe2x80x9d ratio is therefore relatively high.
Another alternative for storing branch prediction information is the non-tagged, n-way cache. Such a cache was proposed by P. Michaud, A. Seznec and R. Uhlig in an article entitled xe2x80x9cTrading Conflict and Capacity Aliasing in Conditional Branch Predictorsxe2x80x9d, which was published by the Association for Computing Machinery, Inc. in 1997. The cache redundantly stores a copy of a given count in each of the cache""s n ways (e.g., each of three ways), but stores the redundant copies in different sets of indexed locations in each of the n ways. The different sets of indexed locations are generated by index hashing functions which are designed to identify a different set of indexed locations in the cache""s n ways for each different address which they receive at their inputs. A cache hit is determined by submitting the address of a count to the n index hashing functions, generating n indexes, reading n indexed counts, and then determining whether a majority of the n counts just read agree (i.e., a hit is determined through voting). If a majority of the counts agree, a hit is signaled and one of the counts in the agreeing majority is output from the cache. Conflict aliasing is minimized on one hand via the index hashing, and on the other hand via the redundancy and voting. For example, consider a 3-way non-tagged cache. If a second count having addressxe2x80x942 overwrites one of the three redundant copies of a first count having addressxe2x80x941, the first count is still considered to exist in the cache if the other two of its three copies still agree. One unique aspect of such a non-tagged, n-way cache is that the advantages of a set-associative cache can be achieved without a need to store tags. Michaud et al.""s article is hereby incorporated by reference for all that it discloses.
Although there are many advantages to Michaud et al.""s cache, the cache still suffers from aliasing due to the fact that the cache holds numerous 2-bit counts, but each of the counts can assume one of only four values (i.e., 00, 01, 10 or 11). As a result, even though different counts are stored in different sets of indexed locations in the cache""s n arrays, the fact remains that many of the counts stored in the cache will be the same count, thus increasing the likelihood of false hits. For example, consider the combination of indexes including indexxe2x80x941 in wayxe2x80x941, indexxe2x80x941 in wayxe2x80x942, and indexxe2x80x941 in wayxe2x80x943. Although a countxe2x80x941 has yet to be written into this combination of indexes, one copy of a countxe2x80x942 may have been written to indexxe2x80x941 in wayxe2x80x941, one copy of a countxe2x80x943 may have been written to indexxe2x80x941 in wayxe2x80x942, and one copy of a countxe2x80x944 may have been written to indexxe2x80x941 in wayxe2x80x943. Since there are only four counts that can be written into the cache, there is a substantial probability that an attempted read of countxe2x80x941 could result in a cache hit even though countxe2x80x941 has never been written into the cache. Better methods and apparatus for reducing false hits in a non-tagged, n-way cache are therefore needed.
The invention comprises a method for reducing false hits in a non-tagged, n-way cache.
In one embodiment of the invention, data values which are provided to a non-tagged, n-way cache are written into the cache in a non-count form. One type of non-count data value which can be written into such a cache is a data value comprising branch prediction history bits.
Although counters tend to quickly saturate to one extreme or the other (e.g., all zeros or all ones), or briefly take on a value which approaches an extreme, non-count data values tend to assume a wider variety of values. Similarly to data hashing, data values that assume a wider variety of values help to reduce false hits from a cache. For example, if a 2-bit counter is saturated at 11 when a branch is all of a sudden not taken, the counter will be decremented to 10. If the branch is then repeatedly taken, the counter will once again saturate at 11 after its next update. However, when two bits of branch prediction history bits are stored in a cache, and a branch is suddenly not taken after a long period of being always taken, the shift of a not taken history bit into the two bit history changes the history bits from 11 to 10. If the branch is then repeatedly taken, the branch history bits change from 10 to 01, and finally to 11 again. The same event therefore produces a wider variety of values when the data stored in a branch prediction cache comprises non-count data. If a 5-bit counter is compared with a 5-bit history, the above discussed event results in no greater change in the 5-bit counter than is seen in the 2-bit counter (each assume two different values). However, the same event produces six combinations of 5-bit histories versus three combinations of 2-bit histories.